package algorithm.sort.quickSort;

import java.util.Arrays;

public class Quick {
    public static void main(String[] args) {
        int[] arr = {19, 97, 9, 17, 1, 8, 27};
        quick1(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));

    }


    public static void quick2(int[] arr, int left, int right) {
        //等号不是必须的，有等号会提高效率
        if (left > right)
            return;
        int l = left;
        int r = right;
        int temp = 0;
        int pivot = arr[left];
        while (r != l) {
            //右边找到小于等于pivot的
            while (arr[r] >= pivot && r > l) {
                r--;
            }
            //左边找到大于等于pivot的
            while (arr[l] <= pivot && l < r) {
                l++;
            }
            //交换这两个值，不写这句话效率降低，r=l的时候还会进行交换，这时直接跳出外层循环就好了
            if (r > l) {
                temp = arr[r];
                arr[r] = arr[l];
                arr[l] = temp;
            }
        }
        //将pivot的重合的值交换
        arr[left] = arr[l];
        arr[l] = pivot;
        //递归，先排左边，再排右边
        quick2(arr, left, r - 1);
        quick2(arr, r + 1, right);
    }


    public static void quick1(int[] arr, int left, int right) {
        if (left > right)
            return;
        //保存中轴值
        int temp = arr[left];
        int l = left;
        int r = right;
        while (l < r) {
            //r左移
            while (arr[r] > temp && r > l) {
                r--;
            }
            if (r > l) {
                arr[l++] = arr[r];
            }
            //l右移
            while (arr[l] < temp && l < r) {
                l++;
            }
            if (l < r) {
                arr[r--] = arr[l];
            }
        }
        //中轴放到合适的位置
        arr[r] = temp;
        //递归
        quick1(arr, left, r - 1);
        quick1(arr, r + 1, right);
    }
}
